package com.sise.Tree;

/**
 *      剑指 Offer 26. 树的子结构
 *
 *      输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
 *      B是A的子结构， 即 A中有出现和B相同的结构和节点值。
 *
 *      例如:
 *      给定的树 A:
 *
 *         3
 *        / \
 *       4  5
 *       / \
 *      1  2
 *      给定的树 B：
 *
 *        4
 *       /
 *      1
 *      返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。
 */
public class _offer_26_isSubStructure {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) return false;
        return (recur(A, B)                         // 检验当前的 A、B 值是否符合要求
                || isSubStructure(A.left, B)        // 如果当前值不符合，那么就检验 A 的左右子节点是否有 相等的 (这里采用的是 或，只要有一个子树满足条件，那么就可以了)
                || isSubStructure(A.right, B));
    }

    private boolean recur(TreeNode A, TreeNode B) { // (递归的返回值)
                                                    // (递归的终止条件)
        if (B == null) return true;                 // 如果 B 为空，那么 B 已经走完了，A 和 B 完美匹配，返回 true。
                                                    // 这一句判断要放在前面，因为 A 此时也可能为空，如果把 A == null 放在前面，在特殊例子下会出问题
        if (A == null) return false;                // 如果 A 为空，那么就说明 A 走到没路了，此时返回 false
        if (A.val != B.val) return false;           // 如果此时的 A 不等于 B 值，那么说明不相等，返回 false

        return recur(A.left, B.left) && recur(A.right, B.right);    // 除了检验当前值，还得检验 A、B 的左右子节点是否相等 (递归的动作)
    }
}
